# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学(博达校区)
职业：学生(2025级研一)
创建时间: 2025/11/21 21:25
功能需求：
设计思路：
代码说明：
备注：

"""
class DynamicArray:
    def __init__(self, initial_capacity=1):
        """
        动态数组 - 一个会自动扩容的数组
        参数:
            initial_capacity: 初始容量，默认1（很小，便于演示扩容）
        """
        self.capacity = initial_capacity  # 当前书包的"格子数"
        self.size = 0  # 当前已经放了几个物品
        self.array = [None] * initial_capacity  # 实际的存储空间
        self.total_cost = 0  # 记录总"成本"（操作次数）

    """
       向动态数组插入一个值，并返回该操作产生的总成本
       成本计算：
           普通插入：成本 = 1（容量未满的情况下，只放一个物品）
           扩容时的插入：成本 = 当前size + 1（复制所有既有物品 + 放新1个物品）
    """
    def insert(self, value):
        # 记录本次操作的开始成本
        operation_cost = 0
        # 检查是否需要扩容（书包是否满了，如果已经满了，则需要扩容后才能放新东西）
        if self.size == self.capacity:
            # 书包满了！需要换大书包 - 昂贵操作
            expansion_cost = self._expand_array()
            operation_cost += expansion_cost
        # 执行普通插入（把物品放进当前格子）
        self.array[self.size] = value
        self.size += 1
        operation_cost += 1  # 普通插入成本+1
        # 记录总成本
        self.total_cost += operation_cost
        return operation_cost

    """
      扩容数组：创建一个2倍大的新数组，复制所有元素
      返回：扩容操作的成本
    """
    def _expand_array(self):
        old_capacity = self.capacity
        new_capacity = self.capacity * 2  # 双倍扩容
        print(f"扩容发生！ {old_capacity} → {new_capacity}, 复制 {self.size} 个元素")
        # 创建新数组（大书包）
        new_array = [None] * new_capacity
        # 复制所有元素到新数组（把旧书包的东西搬到新书包）
        # 这个复制操作的成本 = 当前元素个数
        copy_cost = self.size
        for i in range(self.size):
            new_array[i] = self.array[i]  #这步体现了元素确实随着扩容被同步复制到新数组中去了
        # 更新数组和容量
        self.array = new_array
        self.capacity = new_capacity
        # 扩容总成本 = 复制成本
        return copy_cost

    def aggregate_analysis(self, n_operations):
        """
        聚合分析：执行n次插入操作，分析平摊成本
        参数:
            n_operations: 要执行的插入操作次数
        返回分析结果
        """
        print(f"\n=== 开始执行 {n_operations} 次插入操作 ===")
        # 重置计数器（为了演示）
        self.total_cost = 0
        # 执行n_operations次插入操作
        for i in range(n_operations):
            cost = self.insert(i)
            if cost > 1:  # 只有扩容时成本才大于1
                print(f"  第{i + 1}次插入: 成本 = {cost}")
            else:
                print(f"  第{i + 1}次插入: 成本 = {cost}")
        # 计算平摊成本
        amortized_cost = self.total_cost / n_operations
        print(f"\n聚合分析结果:")
        print(f"总操作次数: {n_operations}")
        print(f"总成本: {self.total_cost}")
        print(f"平摊成本: {amortized_cost:.2f}")
        print(f"当前数组: 大小={self.size}, 容量={self.capacity}")

        return amortized_cost

"""
用小例子详细解释平摊分析的原理
"""
def explain_with_small_example():
    print("=== 平摊分析原理详解(explain_with_small_example方法) ===")
    print("让我们跟踪前8次插入操作：")
    # 创建一个初始容量为1的小容量的数组来演示
    arr = DynamicArray(initial_capacity=1)
    print("操作详情:")
    print("次数\t\t\t\t\t\t\t\t成本\t\t\t\t\t\t\t\t说明")
    print("-" * 100)
    # 执行8次插入，观察成本模式
    for i in range(8):
        cost = arr.insert(i)
        if cost == 1:
            explanation = "普通插入"
        else:
            explanation = f"扩容！复制了{arr.size - 1}个元素 + 插入新元素"
        print(f"{i + 1}\t\t\t\t\t\t\t\t{cost}\t\t\t\t\t\t\t\t{explanation}")

    print("\n关键观察:1. 昂贵操作（扩容）不频繁发生,2. 扩容发生在: 1, 2, 4, 8, 16... 次插入时,3. 大多数操作都是廉价的（成本=1）")


def mathematical_analysis():
    """
    数学分析：为什么平摊成本约等于3
    """
    print("\n=== 数学分析 ===")
    n = 16  # 假设插入16次
    print(f"假设插入 {n} 个元素:")
    print("\n成本分解:")
    # 普通插入成本
    normal_insert_cost = n
    print(f"1. 普通插入成本: {n} × 1 = {normal_insert_cost}")
    # 扩容成本计算
    expansion_cost = 0
    capacities = []  # 记录每次扩容时的容量
    current_capacity = 1
    while current_capacity <= n:
        capacities.append(current_capacity)
        current_capacity *= 2
    print(f"2. 扩容发生时机: {capacities}")

    # 扩容成本 = 每次扩容时复制的元素个数
    expansion_cost = sum(capacities[:-1])  # 最后一次扩容可能不需要
    print(f"   扩容总成本: {sum(capacities[:-1])} = {expansion_cost}")

    # 总成本
    total_cost = normal_insert_cost + expansion_cost
    print(f"3. 总成本: {normal_insert_cost} + {expansion_cost} = {total_cost}")

    # 平摊成本
    amortized_cost = total_cost / n
    print(f"4. 平摊成本: {total_cost} / {n} = {amortized_cost:.2f}")

    print(f"\n结论: 平摊成本 ≈ 3，是常数时间 O(1)!")


def compare_different_sizes():
    """
    比较不同操作次数下的平摊成本
    """
    print("\n=== 不同规模下的平摊成本比较 ===")
    test_sizes = [10, 50, 100, 500, 1000]
    print("操作次数\t平摊成本")
    print("-" * 20)

    for size in test_sizes:
        # 每次测试都创建新的数组
        arr = DynamicArray(initial_capacity=1)
        amortized_cost = arr.aggregate_analysis(size)
        print(f"{size}\t\t{amortized_cost:.4f}")


# 主程序
if __name__ == "__main__":
    print("动态数组的平摊分析演示")
    print("=" * 100)
    # 1. 先用小例子解释原理
    explain_with_small_example()
    # 2. 数学分析
    mathematical_analysis()
    # 3. 实际运行中等规模的测试
    print("\n" + "=" * 100)
    test_array = DynamicArray(initial_capacity=1)
    test_array.aggregate_analysis(16)  # 测试16次插入
    # 4. 比较不同规模
    compare_different_sizes()

    print("\n" + "=" * 100)
    print("总结: 虽然单次插入可能很昂贵（扩容时）但长期来看，平均每次插入的成本约等于3，这就是平摊分析的精髓！")